package com.njupt.DynamicProgramming;

/**
 * 动态规划解决爬楼梯问题
 * 1、dp数组的函数含义
 *      dp[i]表示爬到第i阶楼梯的方法数（dp[i]）
 * 2、确定推导公式
 *      爬到第n阶楼梯，可以通过第n-1阶楼梯爬一步到n阶，此时也是到n-1阶台阶的方法数dp[n-1]
 *                  也可以在n-2阶爬两步到n阶，此时也是表示到n-2阶台阶的方法数dp[n-2]
 *      推导公式为dp[n] = dp[n-1]+dp[n-2]
 * 3、dp数组初始化
 * 4、确定遍历的顺序：从前往后
 */
public class ClimbStairs {

    //采用dp数组式的动态规划
    public int climbStairs(int n) {
        if(n==1){
            return 1;
        }
        if(n==2){
            return 2;
        }
        int[] dp = new int[n+1];
        dp[1] = 1;dp[2] = 2;
        for (int i = 3; i <=n; i++) {
            dp[i] = dp[i-1] + dp[i-2];
        }

        return dp[n];
    }

    //采用迭代式的动态规划,相当于用几个变量表示dp数组，后一个迭代前一个
    public int climbStairs1(int n) {
        if(n==1){
            return 1;
        }
        if(n==2){
            return 2;
        }
        int p=1,q=2,r=3;
        for (int i = 4; i <=n ; i++) {
            p = q;
            q=r;
            r=p+q;
        }
        return r;
    }
    public static void main(String[] args) {
        ClimbStairs test = new ClimbStairs();
        int i = test.climbStairs1(5);
        System.out.println(i);
    }
}
